package Data_Structure.Tree.Test;

//import Data_Structure.Tree.TreeNode;
import java.util.*;

/**
 * @className: Demo1
 * @author: 芃
 * @description: 二叉树相关OJ试题一
 * @date: 2023/8/20 9:40
 */
public class Demo1 {
    public static void main(String[] args) {

    }
    //17、二叉树的镜像-给定一颗二叉树，求他的镜像二叉树
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null){
            return null;
        }
        TreeNode cur = root.left;
        root.left = root.right;
        root.right = cur;
        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;
    }
    //16、二叉树的后序遍历 -非递归
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list1 = new ArrayList<>();
        if (root == null){
            return list1;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        TreeNode prev = null;
        while (cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.peek();//查看一下栈顶元素
            if (top.right == null || top.right == prev){//如果它的右也为空或者遍历过了，就弹出
                stack.pop();
                list1.add(top.val);
                prev = top;
            }else {
                cur = top.right;
            }
        }
        return list1;
    }
    //15、二叉树的中序遍历 -非递归
    //思路：中序-左根右
    //先顺着root一直往左遍历，将所有左节点放到栈中，直到左为空
    //等左为空时，栈中记录了每个左节点的上级路径，即父节点
    //依次弹出栈里面的元素，每拿到一个检测其是否有右节点，有的话再将其作为root节点往左树遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list1 = new ArrayList<>();
        if (root == null){
            return list1;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            list1.add(top.val);
            cur = top.right;
        }
        return list1;
    }

    //14、二叉树的前序遍历 -非递归
    public List<Integer> preorderTraversal3(TreeNode root) {
        Stack<TreeNode> stack = new Stack<>();
        List<Integer> list1 = new ArrayList<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);
                list1.add(cur.val);
                cur = cur.left;
            }
            TreeNode top = stack.pop();
            cur = top.right;
        }
        return list1;
    }

    //13、二叉树的分层遍历
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null){
            return lists;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()){
            int size = queue.size();
            List<Integer> ret = new ArrayList<>();
            for (int j = 0; j < size; j++) {
                TreeNode cur = queue.poll();
                if (cur.left != null){
                    queue.offer(cur.left);
                }
                if (cur.right != null){
                    queue.offer(cur.right);
                }
                ret.add(cur.val);
            }
            lists.add(ret);
        }
        return lists;
    }

    //12、二叉树创建字符串
    public String tree2str(TreeNode root) {
        if (root == null){
            return null;
        }
        StringBuffer stringBuffer = new StringBuffer();
        TreeToString(root,stringBuffer);
        return stringBuffer.toString();
    }
    public void TreeToString(TreeNode t,StringBuffer stringBuffer){
        if (t == null){
            return;
        }
        stringBuffer.append(t.val);
        if (t.left != null){
            stringBuffer.append("(");
            TreeToString(t.left,stringBuffer);
            stringBuffer.append(")");
        }else {
            if (t.right != null){
                stringBuffer.append("()");
            }else {
                return;
            }
        }
        if (t.right != null){
            stringBuffer.append("(");
            TreeToString(t.right,stringBuffer);
            stringBuffer.append(")");
        }else {
            return;
        }
    }

    //11、根据一颗二叉树的前序遍历与中序遍历构造二叉树
    public TreeNode buildTree2(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null){
            return null;
        }
        return createTreeByPandI(preorder,inorder,0,inorder.length - 1);
    }
    public int preIndex = 0;// 前序遍历时的下标，全局共享一份
    public TreeNode createTreeByPandI(int[] preorder,int[] inorder,int inBegin,int inEnd){
        if (inBegin > inEnd){//区间用尽了
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        //在中序遍历的结果中查找root节点所在的位置（root动态变化）
        int rootIndex = findIndexOfInOrder(inorder,inBegin,inEnd,preorder[preIndex]);
        if (rootIndex == -1){
            return null;//说明没找到
        }
        preIndex++;
        root.left = createTreeByPandI(preorder,inorder,inBegin,rootIndex - 1);//在中序遍历结果的左区间
        root.right = createTreeByPandI(preorder,inorder,rootIndex + 1,inEnd);//在中序遍历结果的右区间
        return root;
    }

    //给定key在中序遍历序列当中查找key所在的下标并返回
    public int findIndexOfInOrder(int[] inOrder,int inBegin,int inEnd,int key){
        for (int i = inBegin; i <= inEnd; i++) {
            if (inOrder[i] == key){
                return i;
            }
        }
        return -1;
    }

    //10、根据一颗二叉树的中序遍历与后序遍历构建二叉树
    public TreeNode buildTree3(int[] inorder, int[] postorder) {
        if (inorder == null || postorder == null){
            return null;
        }
        postIndex = postorder.length - 1;
        return createTreeByIandP(postorder,inorder,0,inorder.length-1);
    }
    public int postIndex = 0;
    public TreeNode createTreeByIandP(int[] postorder,int[] inorder,int inBegin,int inEnd){
        if (inBegin > inEnd){
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
        int rootIndex = findIndexOfInOrder(inorder,inBegin,inEnd,postorder[postIndex]);
        if (rootIndex == -1){
            return null;
        }
        postIndex--;
        root.right = createTreeByIandP(postorder,inorder,rootIndex+1,inEnd);
        root.left = createTreeByIandP(postorder,inorder,inBegin,rootIndex-1);

        return root;
    }


    //9、二叉搜索树转换成排序双向链表
    public TreeNode Convert(TreeNode pRootOfTree) {
        if (pRootOfTree == null){
            return pRootOfTree;
        }
        inOrderConvert(pRootOfTree);
        TreeNode head = pRootOfTree;
        while (head.left != null){
            head = head.left;
        }
        return head;
    }
    TreeNode prev = null;
    public void inOrderConvert(TreeNode pCur){
        if (pCur == null){
            return;
        }
        inOrderConvert(pCur.left);
        //打印
        pCur.left = prev;
        if (prev != null){
            prev.right = pCur;
        }
        prev = pCur;
        System.out.print(pCur.val + " ");
        inOrderConvert(pCur.right);
    }

    //8、给定一颗二叉树，找到该树中两个指定节点的最近公共祖先
    // 思路二：假设这课二叉树是使用孩子双亲表示法表示的，就可以把问题转换为链表求交点
    // 借助一个数据结构存储路径-》
    // ①、两个栈，分别存储p、q的寻找路径
    // ②、求栈的大小，为第③步做铺垫
    // ③、让大的栈出差值个元素
    // 为什么要让大栈出差值个元素？
    // 可以想象一下，一个节点深，一个节点浅，则最近公共祖先只会比浅的那个深度小或者相等，因此可以无脑把大栈出差值个元素
    // ④、开始出栈，直到栈顶元素相同，此时栈顶元素即为最近公共祖先
    public TreeNode lowestCommonAncestor3(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null){
            return null;
        }
        Stack<TreeNode> stack1 = new Stack<>();
        Stack<TreeNode> stack2 = new Stack<>();
        getPath(root,p,stack1);
        getPath(root,q,stack2);
        int sub = Math.abs(stack1.size() - stack2.size());//求差值
        if (stack1.size() > stack2.size()){
            while (sub != 0){
                stack1.pop();
                sub--;
            }
        }else {
            while (sub != 0){
                stack2.pop();
                sub--;
            }
        }
        while (!stack1.isEmpty()){
            TreeNode cur1 = stack1.pop();
            TreeNode cur2 = stack2.pop();
            if (cur1 == cur2){
                return cur1;
            }
        }
        return null;
    }
    //获取根节点到目标节点的路径
    //root 根节点
    //target 目标节点
    //stack 存放目标节点的路径
    public boolean getPath(TreeNode root,TreeNode target,Stack<TreeNode> stack){
        if (root == null || target == null){//说明该路径走到头了或者目标节点为空
            return false;
        }
        stack.push(root);//将遍历的该节点放到栈stack中
        if (root.val == target.val){//找到了，就返回true
            return true;
        }
        boolean flg = getPath(root.left,target,stack);//先去左树去找
        if (flg){//找到了就返回true
            return true;
        }
        boolean flg2 = getPath(root.right,target,stack);//走到这，说明左树没找到，再去右树找
        if (flg2){//右树当中如果找到了，就返回true
            return true;
        }
        //走到这说明该路径下没有要找的元素，弹出栈顶元素
        stack.pop();
        return false;//说明该路径下没有目标节点
    }
    // 思路一：如果给定的树是一颗二叉搜索树（根节点的左边都比根小，根节点的右边都比根大）
    // 二叉搜索树的根节点及其子树都为二叉搜索树
    // 二叉搜索树的特点：中序遍历的大小是有序的
    // ①p.val < root.val && q.val > root.val 最近公共祖先为root
    // ②p.val > root.val && q.val < root.val 最近公共祖先为root
    // ③root.val == p.val || root.val == q.val 最近公共祖先为root
    // ④p.val < root.val && q.val < root.val 最近公共祖先在root的左子树当中
    // ⑤p.val > root.val && q.val > root.val 最近公共祖先在root的右子树当中
    //※二叉搜索树当中寻找最近公共祖先
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null){
            return null;
        }
        if (p.val < root.val && q.val > root.val){//①
            return root;
        }
        if (p.val > root.val && q.val < root.val){//②
            return root;
        }
        if (root.val == p.val || root.val == q.val){//③
            return root;
        }
        if (root.val > p.val && root.val > q.val){//④
            return lowestCommonAncestor(root.left,p,q);
        }
        if (root.val < p.val && root.val < q.val){//⑤
            return lowestCommonAncestor(root.right,p,q);
        }
        return null;
    }
    // ※针对普通的二叉树寻找最近公共祖先-》前提：p、q 为不同节点且均存在于给定的二叉树中。
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null){
            return null;
        }
        if (root == p || root == q){//如果是root为p或者q说明找到了p、q其中的一个
            return root;
        }
        TreeNode leftT = lowestCommonAncestor1(root.left,p,q);//去左树找p、q
        TreeNode rightT = lowestCommonAncestor1(root.right,p,q);//去右树找p、q
        if (leftT != null && rightT != null){//如果左右子树都找到了一个，此时说明p、q的最近公共祖先就是root
            return root;
        }else if (leftT != null){//说明右边没找到，则p、q都在root的左树
            return leftT;
        }else if (rightT != null){//说明左边没找到，则p、q都在root的右树
            return rightT;
        }else {
            return null;
        }
    }

    //7、二叉树的构建及其遍历
    public static void main1(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()){
            String str = scanner.nextLine();
            TreeNode root = buildTree(str);
            inOrder(root);
        }
        scanner.close();
    }
    public static int i = 0;
    private static TreeNode buildTree(String str) {
        TreeNode root = null;
        if (str.charAt(i) != '#'){
            root = new TreeNode(str.charAt(i));
            //构建左树
            i++;
            root.left = buildTree(str);
            //构建右树->因为是递归调用的，在left树的递归当中就已经对i进行了++，所以此处不需要++
            root.right = buildTree(str);
        }else {
            i++;
        }
        return root;
    }
    //中序遍历
    public static void inOrder(TreeNode root){
        if (root == null){
            return;
        }
        inOrder(root.left);
        System.out.print(root.val + " ");
        inOrder(root.right);
    }

    //6、对称二叉树
    public boolean isSymmetric(TreeNode root) {
        if (root == null){
            return true;
        }
        return isSymmetricChild(root.left,root.right);
    }
    public boolean isSymmetricChild(TreeNode left,TreeNode right){
        if (left == null && right == null){
            return true;
        }
        if (left == null || right == null){
            return false;
        }
        if (left.val != right.val){
            return false;
        }
        return isSymmetricChild(left.left,right.right) && isSymmetricChild(left.right,right.left);
    }

    //5、判断一棵树是否是平衡二叉树
    // 平衡二叉树：一颗树要是平衡二叉树，那么它的每一棵子树都是平衡二叉树，左右子树的高度差不大于1
    // 时间复杂度：O(n^2) 未优化时 ->isBalanced
    // 优化：在求左右子树高度的时候判断其是否平衡
    //优化后时间复杂度：O(n)->isBalanced2
    public boolean isBalanced2(TreeNode root) {
        if (root == null){
            return true;
        }
        return isBalanceByGetHigh(root) >= 0;
    }
    //在求高度的同时判断是否平衡
    public int isBalanceByGetHigh(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftHigh = isBalanceByGetHigh(root.left);
        int rightHigh = isBalanceByGetHigh(root.right);
        if (leftHigh >= 0 && rightHigh >= 0 && Math.abs(leftHigh - rightHigh) <= 1){
            //平衡
            return Math.max(leftHigh,rightHigh) + 1;
        }else {
            //说明不平衡
            return -1;
        }
    }
    //判断平衡树 未优化代码
    public boolean isBalanced(TreeNode root) {
        if (root == null){
            return true;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if (Math.abs(leftHeight - rightHeight) > 1){
            return false;
        }
        boolean left = isBalanced(root.left);
        boolean right = isBalanced(root.right);
        return left && right;
    }

    //4、二叉树的最大深度
    public int getHeight(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
    }

    //3、判断一棵树是否是另外一颗树的子树
    //时间复杂度：O(m*n) m为root树的节点个数 n为subRoot树的节点个数
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if (root == null || subRoot == null){
            return false;
        }
        //根节点和subRoot是不是两棵相同的树
        boolean flg = isSameTree(root,subRoot);
        if (flg){
            return true;
        }
        //subRoot是不是Root的左子树
        boolean left = isSubtree(root.left,subRoot);
        //subRoot是不是Root的右子树
        boolean right = isSubtree(root.right,subRoot);
        return left || right;
    }

    //2、检查两课树是否相同
    //时间复杂度：O(n) n为p树和q树的 最少节点个数
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (q == null && p != null){
            return false;
        }
        if (q != null && p == null){
            return false;
        }
        if (p == null && q == null){
            return true;
        }
        if (p.val != q.val){
            return false;
        }
        boolean left = isSameTree(p.left,q.left);
        boolean right = isSameTree(p.right,q.right);
        return left && right;
    }

    //1、前序遍历 结果存储到List当中
    // 中序遍历、后序遍历思路相同
    //解法1：
    List<Integer> list = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null){
            return null;
        }
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }
    //解法2：
    public List<Integer> preorderTraversal2(TreeNode root) {
        List<Integer> retlist = new ArrayList<>();
        if (root == null){
            return retlist;
        }
        retlist.add(root.val);
        List<Integer> left = preorderTraversal(root.left);
        retlist.addAll(left);
        List<Integer> right = preorderTraversal(root.right);
        retlist.addAll(right);
        return retlist;
    }
}
